from typing import *

from math import inf


class Solution:

    def maxSumDivThree(self, nums: List[int]) -> int:
        f = [0] * 3
        for num in nums:
            g = f.copy()
            for i in range(3):
                m = (f[i] + num) % 3
                g[m] = max(f[i] + num, g[m])
            f = g.copy()
        return f[0]


so = Solution()
print(so.maxSumDivThree([3, 6, 5, 1, 8]))
print(so.maxSumDivThree([5, 2, 2, 2]))
print(so.maxSumDivThree([4]))
